package com.ainge.easystudy.binary.tree;

import java.util.Comparator;

/**
 * 优先级队列-堆实现
 * 默认最小堆实现，如果需要实现最大堆，请使用comparator控制倒序即可。
 *
 * @author: Ainge
 * @Time: 2021/9/15 20:44
 */
public class SimplePriorityQueue<E> {
    /**
     * 数组
     */
    private transient Object[] array;
    /**
     * 当前队列元素个数
     */
    private int size;
    /**
     * 如果没有指定排序方式的话，
     * 则默认使用元素E的自然排序
     */
    private Comparator<? super E> comparator;

    public SimplePriorityQueue(int initArraySize) {
        array = new Object[initArraySize];
    }

    public SimplePriorityQueue(int initArraySize, Comparator<? super E> comparator) {
        this(initArraySize);
        this.comparator = comparator;
    }

    public void offer(E value) {
        if (size >= array.length) {
            resize();
        }
        array[size++] = value;
        upAdjust();
    }

    public E poll() {
        if (size <= 0) {
            throw new IllegalArgumentException("queue empty now...");
        }
        E first = (E) array[0];
        // heapify
        int s = --size;
        E x = (E) array[s];
        array[s] = null; //gc
        downAdjust(0, x);
        return first;
    }

    /**
     * 堆下沉操作
     *
     * @param k 开始比较的父节点位置
     * @param x 需要与k位置下的左右节点比较的元素
     */
    private void downAdjust(int k, E x) {
        // 从k节点开始下沉
        int half = size >>> 1;
        // 直到最后一个非叶子节点即可，没必要循环到后面的叶子节点
        while (k < half) {
            // left = 2*n + 1
            int minChildIndex = (k << 1) + 1;
            // 假设左孩子为最小
            Object minChild = array[minChildIndex];
            // right = 2*n + 2 = left + 1
            int right = minChildIndex + 1;
            // right < size说明右孩子存在
            if (right < size && this.compare(minChild, array[right]) > 0) {
                // 结果是右孩子最小
                minChild = array[minChildIndex = right];
            }
            // 父亲与最小的孩子比较谁小，若父亲小，说明不需要调整位置。
            if (this.compare(minChild, x) >= 0) {
                break;
            }
            // 将最小值孩子移动到此时父节点位置
            array[k] = minChild;
            // 父亲元素值继续与最小值孩子下面的左右节点比较；
            k = minChildIndex;
        }
        // 最终x元素下沉的位置
        array[k] = x;
    }


    /**
     * 先将插入的元素放入最HeapSize位置，再上浮比较，确定最终位置。
     */
    private void upAdjust() {
        // 最末尾的元素，就是刚刚插入的。
        int childIndex = size - 1;
        // 他的父节点
        int parentIndex;
        // 临时标记该元素
        Object tmp = array[childIndex];
        // 开始寻找该元素最终的下标
        while (childIndex > 0) {
            if (this.compare(tmp, array[parentIndex = (childIndex - 1) >>> 1]) >= 0) {
                // 该元素比此时的父节点大，此时childIndex就是它的位置
                break;
            }
            // 此时它比它父亲小，把此时的下标位置让给它的父亲
            array[childIndex] = array[parentIndex];
            // 它的下标需要与父亲交换。
            childIndex = parentIndex;
        }
        // 找到该元素的最终下标，赋值
        array[childIndex] = tmp;
    }


    private int compare(Object e1, Object e2) {
        E first = (E) e1;
        E next = (E) e2;
        if (comparator != null) {
            return comparator.compare(first, next);
        }
        if (e1 instanceof Comparable) {
            Comparable<? super E> comparable = (Comparable<? super E>) first;
            return comparable.compareTo(next);
        }
        throw new IllegalArgumentException("must support Comparable");
    }

    private void resize() {
        // 数组2倍扩容
        Object[] newArray = new Object[array.length << 1];
        System.arraycopy(array, 0, newArray, 0, array.length);
        array = newArray;
    }


    public static void main(String[] args) {

        Comparator<Integer> asc = Integer::compare;
        Comparator<Integer> desc = (o1, o2) -> -Integer.compare(o1, o2);

        //SimplePriorityQueue<Integer> simplePriorityQueue = new SimplePriorityQueue<>(5);
        SimplePriorityQueue<Integer> simplePriorityQueue = new SimplePriorityQueue<>(5,desc);
        simplePriorityQueue.offer(5);
        simplePriorityQueue.offer(3);
        simplePriorityQueue.offer(4);
        simplePriorityQueue.offer(2);
        simplePriorityQueue.offer(1);
        simplePriorityQueue.offer(7);
        simplePriorityQueue.offer(9);

        System.out.println(simplePriorityQueue.poll());
        System.out.println(simplePriorityQueue.poll());
        System.out.println(simplePriorityQueue.poll());
        System.out.println(simplePriorityQueue.poll());
        System.out.println(simplePriorityQueue.poll());
        System.out.println(simplePriorityQueue.poll());
        System.out.println(simplePriorityQueue.poll());
        // 验证异常
        System.out.println(simplePriorityQueue.poll());
    }

}
